package 单周赛.history;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 */
public class 第311场单周赛 {

    public static void main(String[] args) {

        System.out.println(longestContinuousSubstring("abcde"));

        TreeNode node7 = new TreeNode(3);
        TreeNode node13 = new TreeNode(8);
        TreeNode node11 = new TreeNode(13);
        node7.left = node13;
        node7.right = node11;

        TreeNode node71 = new TreeNode(5);
        TreeNode node131 = new TreeNode(21);
        TreeNode node111 = new TreeNode(34);
        node71.left = node131;
        node71.right = node111;

        TreeNode node2 = new TreeNode(2);
        node2.left = node7;
        node2.right = node71;

        reverseOddLevels(node2);

    }

    public int smallestEvenMultiple(int n) {
        if (n < 2) {
            return 2;
        }
        if (n % 2 == 0) {
            return n;
        }
        return 2 * n;
    }

    /**
     * 动态规划
     *
     * @param s
     * @return
     */
    public static int longestContinuousSubstring(String s) {
        int maxLen = 1;
        int preLen = 1;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) - s.charAt(i - 1) == 1) {
                maxLen = Math.max(maxLen, preLen + 1);
                preLen++;
            } else {
                preLen = 1;
            }
        }

        return maxLen;
    }

    /**
     * 广度优先搜索+双指针
     *
     * @param root
     * @return
     */
    public static TreeNode reverseOddLevels(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        int level = 0;
        while (!queue.isEmpty()) {
            if (level % 2 == 1) {
                TreeNode[] nodes = new TreeNode[queue.size()];
                int left = 0, right = nodes.length - 1;

                while (!queue.isEmpty()) {
                    TreeNode firstNode = queue.pollFirst();
                    TreeNode lastNode = queue.pollLast();

                    replaceVal(firstNode, lastNode);

                    nodes[left] = firstNode;
                    nodes[right] = lastNode;

                    left++;
                    right--;
                }

                for (TreeNode node : nodes) {
                    queue.addLast(node);
                }
            }

            int size = queue.size();
            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                if (curNode.left != null) {
                    queue.addLast(curNode.left);
                }
                if (curNode.right != null) {
                    queue.addLast(curNode.right);
                }
            }
            level++;
        }

        return root;
    }

    private static void replaceVal(TreeNode firstNode, TreeNode lastNode) {
        int fVal = firstNode.val;

        firstNode.val = lastNode.val;

        lastNode.val = fVal;
    }


    /**
     * 字典树
     *
     * @param words
     * @return
     */
    public int[] sumPrefixScores(String[] words) {
        Trie trie = new Trie();

        for (String word : words) {
            // 建树时，比如 "abc" , a位置需要 +1 , b,c的位置也要+1
            // 而不是将word变成，a , ab , abc ,建三次树，到结尾才将结尾元素 +1 !!!
            trie.insert(word);
        }

        int[] answer = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            answer[i] = trie.findScore(words[i]);
        }

        return answer;
    }

    static class Trie {

        private int count = 0;

        private Trie[] childrens = new Trie[26];

        private void insert(String word) {
            Trie curTrie = this;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (curTrie.childrens[idx] == null) {
                    curTrie.childrens[idx] = new Trie();
                }
                curTrie.childrens[idx].count++;
                curTrie = curTrie.childrens[idx];
            }
        }

        private int findScore(String word) {
            int sum = 0;
            Trie curTrie = this;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';

                sum += curTrie.childrens[idx].count;
                curTrie = curTrie.childrens[idx];
            }
            return sum;
        }
    }
}
